package com.zjsru.plan2024.oneday;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @Author: cookLee
 * @Date: 2024-01-31
 * 找出不同元素数目差数组
 */
public class DistinctDifferenceArray {

    /**
     * 主
     * \
     * 输入：nums = [1,2,3,4,5]
     * 输出：[-3,-1,1,3,5]
     * 解释：
     * 对于 i = 0，前缀中有 1 个不同的元素，而在后缀中有 4 个不同的元素。因此，diff[0] = 1 - 4 = -3 。
     * 对于 i = 1，前缀中有 2 个不同的元素，而在后缀中有 3 个不同的元素。因此，diff[1] = 2 - 3 = -1 。
     * 对于 i = 2，前缀中有 3 个不同的元素，而在后缀中有 2 个不同的元素。因此，diff[2] = 3 - 2 = 1 。
     * 对于 i = 3，前缀中有 4 个不同的元素，而在后缀中有 1 个不同的元素。因此，diff[3] = 4 - 1 = 3 。
     * 对于 i = 4，前缀中有 5 个不同的元素，而在后缀中有 0 个不同的元素。因此，diff[4] = 5 - 0 = 5 。
     * \
     * 输入：nums = [3,2,3,4,2]
     * 输出：[-2,-1,0,2,3]
     * 解释：
     * 对于 i = 0，前缀中有 1 个不同的元素，而在后缀中有 3 个不同的元素。因此，diff[0] = 1 - 3 = -2 。
     * 对于 i = 1，前缀中有 2 个不同的元素，而在后缀中有 3 个不同的元素。因此，diff[1] = 2 - 3 = -1 。
     * 对于 i = 2，前缀中有 2 个不同的元素，而在后缀中有 2 个不同的元素。因此，diff[2] = 2 - 2 = 0 。
     * 对于 i = 3，前缀中有 3 个不同的元素，而在后缀中有 1 个不同的元素。因此，diff[3] = 3 - 1 = 2 。
     * 对于 i = 4，前缀中有 3 个不同的元素，而在后缀中有 0 个不同的元素。因此，diff[4] = 3 - 0 = 3 。
     * \
     * @param args
     */
    public static void main(String[] args) {
        DistinctDifferenceArray distinctDifferenceArray = new DistinctDifferenceArray();
        int[] nums = new int[]{1,2,3,4,5};
        System.out.println(Arrays.toString(distinctDifferenceArray.distinctDifferenceArray(nums)));
    }

    /**
     * 模拟
     * @param nums nums
     * @return {@link int[]}
     */
    public int[] distinctDifferenceArray(int[] nums) {
        int len = nums.length;
        //利用set特性将相同的数字过滤出去
        Set<Integer> set = new HashSet<>();
        //定义一个数组记录每个下标时的数字多少
        int[] lenNum = new int[len + 1];
        //从后遍历
        for (int i = len - 1; i > 0; i--) {
            set.add(nums[i]);
            lenNum[i] = set.size();
        }
        int[] res = new int[len];
        //清空set，复用
        set.clear();
        //从来开始遍历并与之前获取的数组相减即是答案
        for (int i = 0; i < len; i++) {
            set.add(nums[i]);
            res[i] = set.size() - lenNum[i + 1];
        }
        return res;
    }

}
